package wumpus;

import java.io.*;
import java.util.*;

/** Implements a human controlled agent. **/
public class SimpleAgent implements WumpusAgent
{
    int width, height;
	
    int breezy[][], smelly[][], glimmery[][], safe[][], explore[][], visited[][];
    int agentx, agenty;
	
    boolean hasGold;
    boolean hasShot;
	boolean noSolution;
	boolean forceSolution;
	
    int smellyspots;
	int fcount;
	
    public void init(int width, int height)
    {
        this.width = width;
        this.height = height;
		
		hasGold = false;
		hasShot = false;
		noSolution = false;
		forceSolution = false;
		smellyspots = 0;
		fcount = 0;
		
        breezy = new int[height][width];
        smelly = new int[height][width];
        glimmery = new int[height][width];
        safe = new int[height][width];
        explore = new int[height][width];
        visited = new int[height][width];
		
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                breezy[y][x] = -1;
                smelly[y][x] = -1;
                glimmery[y][x] = -1;
                safe[y][x] = -1;
                explore[y][x] = -1;
                visited[y][x] = -1;
            }
        }
    }
	
	
	private void printBoard() {
        ////////////////////////////////////////////////////
        // Display playing board
        for (int x = 0; x < width; x++)
            System.out.printf("======");
        System.out.printf("=\n");
		
		smellyspots = 0;
        for (int y = height-1; y >= 0; y--) {
            for (int x = 0; x < width; x++) {
				
                System.out.printf("| ");
				
                if (y==agenty && x==agentx)
                    System.out.printf("A");
                else
                    System.out.printf(" ");
				
                if (breezy[y][x] == -1)
                    System.out.printf("?");
                else if (breezy[y][x] == 0)
                    System.out.printf(" ");
                else
                    System.out.printf("B");
				
                if (smelly[y][x] == -1)
                    System.out.printf("?");
                else if (smelly[y][x] == 0)
                    System.out.printf(" ");
                else {
                    System.out.printf("S");
					smellyspots++;
				}
				
                if (glimmery[y][x] == -1)
                    System.out.printf("?");
                else if (glimmery[y][x] == 0)
                    System.out.printf(" ");
                else
                    System.out.printf("G");
            }
			
            System.out.printf("|\n");
        }
		
        for (int x = 0; x < width; x++)
            System.out.printf("======");
        System.out.printf("=\n");    
    }
	
    public void printSafe() {
        ////////////////////////////////////////////////////
        // Display safe board
        for (int x = 0; x < width; x++)
            System.out.printf("=====");
        System.out.printf("=\n");
		
        for (int y = height-1; y >= 0; y--) {
            for (int x = 0; x < width; x++) {
				
                System.out.printf("| ");
				
                if (safe[y][x] == -1) {
                    System.out.printf(" ? ");
				} else {
					if ( safe[y][x] < 0 ) {
						System.out.printf("" + safe[y][x] + " ");
					} else {
						System.out.printf(" " + safe[y][x] + " ");
					}
				}
            }
            System.out.printf("|\n");
        }
		
        for (int x = 0; x < width; x++)
            System.out.printf("=====");
        System.out.printf("=\n");
    }
	
    public void printExplore() {
        ////////////////////////////////////////////////////
        // Display explore board
        for (int x = 0; x < width; x++)
            System.out.printf("=====");
        System.out.printf("=\n");
		
        for (int y = height-1; y >= 0; y--) {
            for (int x = 0; x < width; x++) {
				
                System.out.printf("| ");
				
                if (explore[y][x] == -1) {
                    System.out.printf(" ? ");
				} else {
					if ( safe[y][x] < 0 ) {
						System.out.printf("" + safe[y][x] + " ");
					} else {
						System.out.printf(" " + safe[y][x] + " ");
					}
				}
			}
			
			System.out.printf("|\n");
		}
		
		for (int x = 0; x < width; x++)
			System.out.printf("=====");
        System.out.printf("=\n");
	}
	
	
	
	
	
	private void resetExplore() {
		for (int y = 0; y < height; y++) {
			for (int x = 0; x < width; x++) {
				explore[y][x] = safe[y][x];
			}
		}
	}
	
	private boolean isGoal( String dest, int y, int x ) {
		//printSafe();
		if ( dest == "safe" ) {
			if ( visited[y][x] < 1 ) {
				return true;
			} 
		} else if ( dest == "hunt" ) {
			if ( smelly[y][x] == 1 ) {
				return true;
			}
		} else if ( dest == "home" ) {
			if ( y == 0 && x == 0 ) {
				return true;
			}
		}
		return false;
	}
	
	private void addToQueue( Queue<String> myq, int y, int x, int dist, String currstring, String dir ) {
		String tstring ="";
		
		if ( onBoard( y, x ) && safe[y][x] > -2 ) {
			if ( explore[y][x] <= 1 || ( dist < explore[y][x] && explore[y][x] < 9 ) ) {
				tstring = dir + dist + y + x;
				explore[y][x] = dist;
				myq.add( currstring + tstring );
				//System.out.println( "Added to queue: " + currstring + tstring + "\n");
			}
		}
	}		
	
	private String planMove( String dest ) {
		
		boolean goalFound = false;
		Queue<String> myq = new LinkedList<String>();
		
		int curr_y = agenty;
		int curr_x = agentx;
		int dist = 1;
		String tstring = "";
		String currstring = "";	
		String goalString = "";
		explore[curr_y][curr_x] = 9;
		
		int notGoalCount = 0;
		
		do {					
			addToQueue( myq, curr_y+1, curr_x, dist, currstring, "N");
			addToQueue( myq, curr_y, curr_x+1, dist, currstring, "E");
			addToQueue( myq, curr_y-1, curr_x, dist, currstring, "S");
			addToQueue( myq, curr_y, curr_x-1, dist, currstring, "W");
			
			if ( !myq.isEmpty() ) {
				currstring = myq.remove();
				curr_x = Integer.parseInt(Character.toString(currstring.charAt(currstring.length() - 1)));
				curr_y = Integer.parseInt(Character.toString(currstring.charAt(currstring.length() - 2)));
				dist = Integer.parseInt(Character.toString(currstring.charAt(currstring.length() - 3))) + 1;
				//System.out.println("currstring: " + currstring + " curr_x: " + curr_x + " curr_y: " + curr_y + "\n");
				notGoalCount = 0;
			}
			
			if ( isGoal( dest, curr_y, curr_x ) ) {
				goalFound = true;
				goalString = Character.toString( currstring.charAt(0) );
			} else {
				notGoalCount++;
			}
			
			if (notGoalCount > 10 ) {
				//System.out.println("NO SOLUTION");
				noSolution = true;
				dest = "hunt";
				if ( smellyspots < 1) {
					//SHRUGSystem.out.println("CHANGING SOMETHING RANDOMLY?");
					forceSolution = true;
					if ( onBoard(agenty, agentx+1) && safe[agenty][agentx+1] < -1 ) {
						safe[agenty][agentx+1] = -1;
						noSolution = false;
					} else if ( onBoard(agenty+1, agentx) && safe[agenty+1][agentx] < -1 ) {
						safe[agenty+1][agentx] = -1;
						noSolution = false;
					} else if ( onBoard(agenty, agentx+1) && safe[agenty][agentx+1] < -1 ) {
						safe[agenty][agentx+1] = -1;
						noSolution = false;
					} else if ( onBoard(agenty-1, agentx) && safe[agenty-1][agentx] < -1 ) {
						safe[agenty-1][agentx] = -1;
						noSolution = false;
					} else if ( onBoard(agenty, agentx-1) && safe[agenty][agentx-1] < -1 ) {
						safe[agenty][agentx-1] = -1;
						noSolution = false;
					} else {
						// find the first -4 and flip it to take a chance, better to die trying!
						noSolution = false;
						for (int y = 0; y < height; y++) {
							for (int x = 0; x < width; x++) {
								if ( safe[y][x] == -4 ) {
									safe[y][x] = -1;
									return "SHRUG";
								}
								
							}
						}
						
					}
					return "SHRUG";
				} else {
					return "SHRUG";
				}
			}
			
			//printExplore();
		} while ( !goalFound );
		
		if ( goalFound ) {
			return "MOVE " + goalString;
		} else {
			return "SUICIDE";
		}
	}
	
	private String nextMove( String goal ) {
		String move = "SUICIDE";
		resetExplore();
		
		if ( goal == "leave" ) {
			if ( agentx == 0 && agenty == 0 ) {
				move = "LEAVE";
			} else {
				move = planMove( "home" );
			}
		} else if ( goal == "explore" ) {
			move = planMove( "safe" );
		} else if ( goal == "shoot" ) {
			if ( smelly[agenty][agentx] == 1 ) {
								
				if ( smellyspots > 1 ) {
					// shoot the wumpus!
					if ( onBoard( agenty-1, agentx-1) && smelly[agenty-1][agentx-1] > 0 ) {
						if ( safe[agenty-1][agentx] > -1 ) {
							move = "SHOOT W";
							hasShot = true;
							noSolution = false;
						} else {
							move = "SHOOT S";
							hasShot = true;
							noSolution = false;
						}
					} else if ( onBoard( agenty+1, agentx+1) && smelly[agenty+1][agentx+1] > 0 ) {
						if ( safe[agenty+1][agentx] > -1 ) {
							move = "SHOOT E";
							hasShot = true;
							noSolution = false;
						} else {
							move = "SHOOT N";
							hasShot = true;
							noSolution = false;
						}
					} else if ( onBoard( agenty-1, agentx+1) && smelly[agenty-1][agentx+1] > 0 ) {
						if ( safe[agenty-1][agentx] > -1 ) {
							move = "SHOOT E";
							hasShot = true;
							noSolution = false;
						} else {
							move = "SHOOT S";
							hasShot = true;
							noSolution = false;
						}
					} else if ( onBoard( agenty+1, agentx-1) && smelly[agenty+1][agentx-1] > 0 ) {
						if ( safe[agenty+1][agentx] > -1 ) {
							move = "SHOOT W";
							hasShot = true;
							noSolution = false;
						} else {
							move = "SHOOT N";
							hasShot = true;
							noSolution = false;
						}
					}
						
				} else if ( smellyspots == 1 && noSolution ) {
					if ( agenty == 0 && agentx == 0 ) {
						safe[agenty][agentx+1] = -1;
						hasShot = true;
						move = "SHOOT E";
						noSolution = false;
					} else if ( onBoard(agenty+1, agentx) && safe[agenty+1][agentx] < -1 ) {
						safe[agenty+1][agentx] = -1;
						hasShot = true;
						move = "SHOOT N";
						noSolution = false;
					} else if ( onBoard(agenty, agentx+1) && safe[agenty][agentx+1] < -1 ) {
						safe[agenty][agentx+1] = -1;
						hasShot = true;
						move = "SHOOT E";
						noSolution = false;
					} else if ( onBoard(agenty-1, agentx) && safe[agenty-1][agentx] < -1 ) {
						safe[agenty-1][agentx] = -1;
						hasShot = true;
						move = "SHOOT S";
						noSolution = false;
					} else if ( onBoard(agenty, agentx-1) && safe[agenty][agentx-1] < -1 ) {
						safe[agenty][agentx-1] = -1;
						hasShot = true;
						move = "SHOOT W";
						noSolution = false;
					} else {
						move = "SUICIDE";
					}
					
				} else {
					move = planMove("hunt");
				}
				
			} else {
				move = planMove("hunt");
			}
		}
		return move;
	}
	
	private boolean onBoard( int y, int x ) {
		if ( ( x > -1 ) && ( x < 4 ) && ( y > -1 ) && ( y < 4 ) ) return true;
		return false;
	}
	
	
	public String getMove(boolean breeze, boolean stench, boolean glimmer)
	{
		////////////////////////////////////////////////////
		// Get move
		
		breezy[agenty][agentx] = breeze ? 1 : 0;
		smelly[agenty][agentx] = stench ? 1 : 0;
		glimmery[agenty][agentx] = glimmer ? 1 : 0;
		safe[agenty][agentx] = 1;
		visited[agenty][agentx] = 1;
		
		String move;
		
		if ( !breeze && !stench ) {
			if ( onBoard( agenty+1, agentx ) ) {
				safe[agenty+1][agentx] = 0;
			}
			if ( onBoard( agenty-1, agentx ) ) {
				safe[agenty-1][agentx] = 0;
			}
			if ( onBoard( agenty, agentx+1 ) ) {
				safe[agenty][agentx+1] = 0;
			}
			if ( onBoard( agenty, agentx-1 ) ) {
				safe[agenty][agentx-1] = 0;
			}
		} else if ( breeze && !forceSolution ) {
			if ( onBoard( agenty+1, agentx ) && ( safe[agenty+1][agentx] == -1 || safe[agenty+1][agentx] == -3 ) ) {
				safe[agenty+1][agentx] -= 3;
			}
			if ( onBoard( agenty-1, agentx ) && ( safe[agenty-1][agentx] == -1 || safe[agenty-1][agentx] == -3 ) ) {
				safe[agenty-1][agentx] -= 3;
			}
			if ( onBoard( agenty, agentx+1 ) && ( safe[agenty][agentx+1] == -1 || safe[agenty][agentx+1] == -3 ) ) {
				safe[agenty][agentx+1] -= 3;
			}
			if ( onBoard( agenty, agentx-1 ) && ( safe[agenty][agentx-1] == -1 || safe[agenty][agentx-1] == -3 ) ) {
				safe[agenty][agentx-1] -= 3;
			}
		} else if ( stench && !hasShot ) {
			if ( onBoard( agenty+1, agentx ) && ( safe[agenty+1][agentx] == -1 || safe[agenty+1][agentx] == -4 ) ) {
				safe[agenty+1][agentx] -= 2;
			}
			if ( onBoard( agenty-1, agentx ) && ( safe[agenty-1][agentx] == -1 || safe[agenty-1][agentx] == -4 ) ) {
				safe[agenty-1][agentx] -= 2;
			}
			if ( onBoard( agenty, agentx+1 ) && ( safe[agenty][agentx+1] == -1 || safe[agenty][agentx+1] == -4 ) ) {
				safe[agenty][agentx+1] -= 2;
			}
			if ( onBoard( agenty, agentx-1 ) && ( safe[agenty][agentx-1] == -1 || safe[agenty][agentx-1] == -4 ) ) {
				safe[agenty][agentx-1] -= 2;
			}
		}
		
		printBoard();
		//printSafe();
		
		if ( (hasGold && hasShot ) || ( noSolution && hasShot) || ( fcount > 10 ) ) { // gtfo
			move = nextMove( "leave" );
		} else if ( smelly[agenty][agentx] > 0 && smellyspots > 1 && !hasShot ) { // shoot the wumpus!
			move = nextMove( "shoot" );
			hasShot = true;
		} else if ( glimmery[agenty][agentx] > 0 ) { // reflexive
			move = "GRAB";
			hasGold = true;
		} else if ( hasGold || noSolution ) { // hunt the wumpus
			move = nextMove( "shoot" );
		} else { // explore 
			move = nextMove( "explore" );
		}
		
		
		String toks[] = move.split("\\s+");
		if (toks[0].equals("MOVE")) {
			
			if (toks.length == 3) {
				agentx += Integer.parseInt(toks[1]);
				agenty += Integer.parseInt(toks[2]);
			} else if (toks[1].equals("N"))
				agenty++;
			else if (toks[1].equals("S"))
				agenty--;
			else if (toks[1].equals("E"))
				agentx++;
			else if (toks[1].equals("W"))
				agentx--;
		}
		
		if ( forceSolution && !noSolution ) {
			forceSolution = false;
			fcount++;
		}
		
		System.out.printf("> " + move + "\n");
		return move;
	}
}
